#include "string_array.h"

using namespace std;

myStr::myStr(const char* str) {
    length = 0;
    while (str[length] != '\0') {
        length++;
    }  
    data = new char[length + 1]; 
    
    for (int i = 0; i < length; i++) {
        data[i] = str[i];
    }
    data[length] = '\0'; 
}

myStr::~myStr() {
    delete[] data; 
}

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int sIndex = start - 1; 
    int sLength = S.getLength();
    int tLength = T.getLength();
    int vLength = V.getLength();

    for (int i = sIndex; i <= sLength - tLength; i++) {
        int j;
        for (j = 0; j < tLength; j++) {
            if (S.data[i + j] != T.data[j]) {
                break; 
            }
        }
        if (j == tLength) { 
            int newLength = sLength - tLength + vLength;

            char* newData = new char[newLength + 1]; 
            for (int k = 0; k < i; k++) {
                newData[k] = S.data[k];
            }
            for (int k = 0; k < vLength; k++) {
                newData[i + k] = V.data[k];
            }
            for (int k = i + tLength; k < sLength; k++) {
                newData[k - tLength + vLength] = S.data[k];
            }
            newData[newLength] = '\0'; 

            delete[] S.data;
            S.data = newData; 
            S.length = newLength; 

            return true; 
        }
    }
    return false; 
}

void myStr::kmp_next() {
    next = new int[length]; 
    int i = 0, k = -1; 
    next[0] = 0; 
    while (i < length) {
        if (data[k] == data[i] || k == -1) { 
            k++; 
            next[++i] = k + 1;
        }
		else
        	k = next[k] - 1;  
    }
}

void myStr::kmp_nextVal() {
    kmp_next(); 
    nextVal = new int[length];
    nextVal[0] = 0; 
    for (int j = 1; j < length; j++) {
        if (data[j] == data[next[j] - 1]) {
            nextVal[j] = nextVal[next[j] - 1];
        } else {
            nextVal[j] = next[j];
        }
    }
}

int simpleMatch(const myStr& S, const myStr& T) {
    int m = S.getLength();  
    int n = T.getLength();  

    if (n > m) 
        return -1;

    for (int i = 0; i <= m - n; ++i) {
        int j = 0;
        while (j < n && S.data[i + j] == T.data[j]) 
            j++;
        if (j == n) 
            return i + 1;  
    }
    return -1;
}

int kmpMatch(const myStr& S, const myStr& T) {
    int n = S.getLength();
    int m = T.getLength();
    if (n < m)
        return -1;
 	int i = 0, j = 0;
    while (i < n) {
        if (T.data[j] == S.data[i]) {
            i++;
            j++;
        }
        if (j == m)
            return i - j + 1;
        else if (i < n && T.data[j] != S.data[i]) {
            if (j != 0)
                j = T.nextVal[j - 1];
            else
                i++;
        }
    }
    return -1;
}

myMatrix::myMatrix() : nodeList(nullptr), rowNum(0), colNum(0), nodeNum(0) {}

myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* data) {
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    nodeList = new matrixNode[nodeNum];

    for (int i = 0; i < nodeNum; i++) {
        nodeList[i].row = data[i * 3];
        nodeList[i].col = data[i * 3 + 1];
        nodeList[i].value = data[i * 3 + 2];
    }

    for (int i = 1; i < nodeNum; i++) {
        matrixNode key = nodeList[i];
        int j = i - 1;
   
        while (j >= 0 && (nodeList[j].row > key.row ||
            (nodeList[j].row == key.row && nodeList[j].col > key.col))) {
            nodeList[j + 1] = nodeList[j];
            j = j - 1;
        }
        nodeList[j + 1] = key;
    }
}

myMatrix::~myMatrix() {
    delete[] nodeList;
}

void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;

    if (nodeNum == 0) {
        T.nodeList = nullptr;
        return;
    }

    T.nodeList = new matrixNode[nodeNum];
    int* rowCount = new int[colNum](); 
    int* rowStart = new int[colNum];    

    for (int i = 0; i < nodeNum; i++) {
        rowCount[nodeList[i].col]++;
    }

    rowStart[0] = 0;
    for (int i = 1; i < colNum; i++) {
        rowStart[i] = rowStart[i - 1] + rowCount[i - 1];
    }

    for (int i = 0; i < nodeNum; i++) {
        int j = rowStart[nodeList[i].col]++;
        T.nodeList[j].row = nodeList[i].col;
        T.nodeList[j].col = nodeList[i].row;
        T.nodeList[j].value = nodeList[i].value;
    }

    delete[] rowCount;
    delete[] rowStart;
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

